package com.atguigu.sort;

import java.util.Arrays;

/**
 * description:希尔排序
 * Created by 才睡醒 on 2021-06-24
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    //交换法
    public static void shellSort(int[] arr) {
        int temp = 0;
        for (int step = arr.length / 2; step > 0; step /= 2) {
            for (int i = step; i < arr.length; i++) {
                for (int j = i - step; j >= 0; j -= step) {
                    if (arr[j] > arr[j + step]) {
                        temp = arr[j];
                        arr[j] = arr[j + step];
                        arr[j + step] = temp;
                    }
                }
            }
        }
    }

    //移位法
    public static void shellSort2(int[] arr){
        for (int step = arr.length/2; step >0 ; step/=2) {
            //从第step个元素，逐个对其所在的组进行直接插入排序
            for (int i = step; i < arr.length; i++) {
                int j = i;
                int temp = arr[j];
                if(arr[j] < arr[j-step]){
                    while (j-step >= 0 && temp < arr[j-step]){
                        //移动
                        arr[j] = arr[j-step];
                        j-=step;
                    }
                    arr[j] = temp;
                }
            }
        }
    }
}
